package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
 * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
 * 557. 反转字符串中的单词 III
 */
public class LeetCode557 {
    /**
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */
    public String reverseWords(String s) {
        StringBuilder builder = new StringBuilder();
        String[] sArr = s.split(" ");
        for (int i = 0; i < sArr.length; i++) {
            char[] c = sArr[i].toCharArray();
            for (int j = 0, k = c.length - 1; j < k; j++, k--) {
                char t = c[j];
                c[j] = c[k];
                c[k] = t;
            }
            builder.append(c);
            if (i != sArr.length - 1) {
                builder.append(" ");
            }
        }
        System.out.println(sArr.length);
        return builder.toString();
    }

    /**
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */
    public String reverseWords1(String s) {
        StringBuilder builder = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            int start = i;
            while (i < s.length() && s.charAt(i) != ' ') {
                i++;
            }
            for (int j = i - 1; j >= start; j--) {
                builder.append(s.charAt(j));
            }
            i++;
            builder.append(' ');
        }
        return builder.toString().trim();
    }

    public static void main(String[] args) {
        String s = "Let's take LeetCode contest";
        LeetCode557 leetCode557 = new LeetCode557();
        System.out.println(leetCode557.reverseWords1(s));
    }
}
